package lib

import "sort"

func init() {
	Probs = append(Probs, Problem{
		Num:         452,
		Discription: "用最少的箭射爆所有气球",
		Level:       2,
		Labels: map[string]int{
			"多元排序": 1,
			"贪心":   1,
		},
	})
}

//每一箭的位置必定是某个气球的右区间，这样能使箭的覆盖范围最大
//根据右区间排序
//从第一个右区间开始作为射箭的位置，遍历所有左区间<=射箭的位置的气球，直到第一个左区间大于射箭的位置的气球，将箭数+1
//从下一个气球的右区间作为下一箭的位置，继续遍历，直到所有气球都射完
func FindMinArrowShots(points [][]int) int {
	sort.Slice(points, func(i, j int) bool {
		return points[i][1] < points[j][1]
	})

	shootX := points[0][1]
	i := 0
	res := 0
	for {
		for i < len(points) && points[i][0] <= shootX {
			i++
		}

		res++
		if i == len(points) {
			break
		}

		shootX = points[i][1]
	}

	return res
}
